\begin{abstract}
Efficiently processing queries against very large graphs is an important
research topic largely driven by emerging real world applications ranging 
from XML databases, GIS, web mining, social network analysis, ontologies,
and bioinformatics etc.  In particular, graph reachability has
attracted a lot of research attention as reachability queries are not only
common on graph databases, but also serves as a fundamental
operator for many other graph queries.  The main idea behind answering
reachability queries in graphs is to build indexes based on reachability labels.
Essentially, each vertex in the graph is assigned certain labels
such that the reachability between any two vertices can be determined
by their labels. Several approaches have been proposed for building these 
reachability labels among them include interval labeling (tree cover) and 2-hop labeling.
However, due to the large number of vertices in many real world 
graphs (some graphs can easily contain millions of vertices) the
computational cost and (index) size of the labels using existing methods 
would prove too expensive to be practical.  
In this paper, we introduce a novel graph structure, referred to as {\em path-tree}, to help labeling very large graphs.  
The path-tree cover is a spanning subgraph of $G$ in a tree shape.
We demonstrate both analytically and
empirically that the effectiveness of our new approaches. 
\end{abstract}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "Paper"
%%% End: 